#!/usr/bin/env python
# -*- coding: utf-8 -*-
#       miia1.py
#       
#       Copyright 2010 santiago <santiagopaleka@gmail.com>
#       
#       This program is free software; you can redistribute it and/or modify
#       it under the terms of the GNU General Public License as published by
#       the Free Software Foundation; either version 2 of the License, or
#       (at your option) any later version.
#       
#       This program is distributed in the hope that it will be useful,
#       but WITHOUT ANY WARRANTY; without even the implied warranty of
#       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#       GNU General Public License for more details.
#       
#       You should have received a copy of the GNU General Public License
#       along with this program; if not, write to the Free Software
#       Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
#       MA 02110-1301, USA.
import random as r
import time as t
tablaDistancias = ((2,1,2,1,0,1,2,1,2),(0,1,2,1,2,3,2,3,4),(1,0,1,2,1,2,3,2,3),
    (2,1,0,3,2,1,4,3,2),(3,2,1,2,1,0,3,2,1),(4,3,2,3,2,1,2,1,0),
    (3,2,3,2,1,2,1,0,1),(2,3,4,1,2,3,0,1,2),(1,2,3,0,1,2,1,2,3))
    
libertades = ((1,3),(0,4,2),(1,5),(0,4,6),(1,3,5,7),(2,4,8),(3,7),(6,4,8),(5,7))
fin = (1,2,3,8,0,4,7,6,5)
def main():
    items = cuadrado()
    items.imprimir()  
    print ""
    items.desordenar()
    items.imprimir()  
    print "el tablero tiene " + str(items.cuantosMal())+ " posiciones mal"
    #~ print items.distancias()   
    #~ print items.calcosto()
    print ""
    while raw_input() != "quit":
        items.ordenar() 
    return
    
class cuadrado:
    def __init__(self,tablero = [1,2,3,8,0,4,7,6,5]):
        self.tablero= tablero
        self.costo = self.calcosto()
        return None
    def imprimir(self):
        for j in range(0,7,3):
            for i in range(3): print(str(self.tablero[i+j])+" |"),
            print "\n-----------"
    def desordenar(self):
        """desordena los items del atributo tablero"""
        r.shuffle(self.tablero)
    def cuantosMal(self):
        """cuenta cuantos elementos de la lista están en su lugar deseado"""
        mal = 0
        for i in range(9):
            if self.tablero[i] != fin[i]:
                mal+=1
        return mal
    def distancias(self):
        dist = 0
        for i in range(9):
            donde = self.tablero.index(i)
            dist +=  tablaDistancias[i][donde]
        return dist
        
    def calcosto(self):
        return self.cuantosMal()+self.distancias()
        
    def ordenar(self,movimientos = 0):
        self.h = self.distancias() + self.cuantosMal()
        if self.h == 0:
            return movimientos
        tableros=[]
        donde = self.tablero.index(0)
        print "el cero está en: " + str(donde) +"\n"
        for i in libertades[donde]:
            padre = self.tablero[:]
            aux = padre[i]
            padre[i] = padre[donde]
            padre[donde]= aux
            tableros.append(cuadrado(padre))
            tableros[-1].imprimir()
            print tableros[-1].costo
        num = 50
        for i in tableros:
            if i.distancias() < num:
                num = i.distancias()
                mejortablero = i
        mejortablero.imprimir()
        self.tablero = mejortablero.tablero
        return
        
        
if __name__ == '__main__': main()
